Bit sequences results, for instance, from encoding digital multimedia content like audio, video, combinations thereof or side information accompanying such content. Or such bit sequences may result from encoding signed integers representing geometry data which specify locations of vertices of three-dimensional mesh models. Encoding such bit sequences further, such that a compact representation of the encoded content and/or of the side information is achieved, is crucial for efficient use of storage capacities and transmission bandwidth.
Each bit sequence may also be understood as consisting of runs of Zeroes alternating with runs of Ones wherein each run is a contiguous sub-sequence of one or more equally valued bits which is immediately followed and immediately preceded by another run of bits each having a different bit value as long as the run is neither the very first nor the very last run of the bit sequence.
In bit sequences, bits of a first possible bit value and bits of a different second possible bit value commonly occur with significantly different frequencies, e.g. Zeroes are more likely than Ones or vice versa. Then, entropy of the bit sequence is smaller than the number of bits comprised in the bit sequence.
If so, there is redundancy in the bit sequence which can be removed by lossless compression.
It is known to use an entropy coding method for lossless compression of bit sequences. Basically, there are three kinds of entropy coding method: (1) variable length coding (VLC), like Huffman coding, (2) arithmetic coding, and (3) dictionary-based compression, like Lempel-Ziv compression or Lempel-Ziv-Welch compression.
The effect of entropy coding is that, difference between entropy of the compressed bit sequence and number of bits comprised in the compressed bit sequence is smaller than difference between entropy of and number of bits comprised in the bit sequence prior to compression.
There is ongoing effort in the art for improving encoding.